package com.zp.self.module.level_4_算法练习.算法.二分查找;

/**
 * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
 * 请必须使用时间复杂度为 O(log n) 的算法。
 * 示例 1:
 * 输入: nums = [1,3,5,6], target = 5
 * 输出: 2
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/search-insert-position
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/remove-element
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class 力扣_35_搜索插入位置 {
    public static void main(String[] args) {
        System.out.println(new 力扣_35_搜索插入位置().searchInsert2(new int[]{1,3,5,6},5));
        System.out.println(new 力扣_35_搜索插入位置().searchInsert2(new int[]{1,3,5,6},2));
        System.out.println(new 力扣_35_搜索插入位置().searchInsert2(new int[]{1,3,5,6},7));
        System.out.println(new 力扣_35_搜索插入位置().searchInsert2(new int[]{1},0));
    }
    public int searchInsert(int[] nums, int target) {
        //遍历,对比当前值与目标值的大小 .{target>nums[i] i++ , target<nums[i] return i, target=nums[i]  return i}
        for (int i = 0; i < nums.length; i++) {
            if(target<= nums[i]) return i;
        }
        return  nums.length;
    }
    /**
     题目：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
     请必须使用时间复杂度为 O(log n) 的算法。

     示例 1:
     输入: nums = [1,3,5,6], target = 5
     输出: 2

     示例 2:
     输入: nums = [1,3,5,6], target = 2
     输出: 1

     示例 3:
     输入: nums = [1,3,5,6], target = 7
     输出: 4

     示例 4:
     输入: nums = [1,3,5,6], target = 0
     输出: 0


     分析：
     1.就是在考二分法啊

     边界值 & 注意点：
     1.
     **/

    //二分法第一种写法：
    //代码中定义 target 是在一个在左闭右闭的区间里，**也就是[left, right] （这个很重要）**
    public static int searchInsert2(int[] nums, int target) {
        //循环,当left<=right   int middle = (left + right)/2
        // nums[middle] > target, target 在左区间，所以[left, middle - 1]
        // nums[middle] < target, target 在右区间，所以[middle + 1, right]
        //注意总共会出现4种情况：
        //0.目标值在数组所有元素之前  [0, -1]   return right + 1  即:0
        //1.目标值等于数组中某一个元素  return middle;
        //2.目标值插入数组中的位置 [left, right]   return  right + 1 ;--注意：这里我们回到最后一轮比较 分析情况
        //  此时必定满足：left == right == middle  ,
        //    若：nums[middle] == nums[right]  > target -- 此时：target 在左区间，所以[left, middle - 1] 故： right = middle - 1 ,所以最后要+1
        //    若：nums[middle] == nums[right]  < target -- 此时：应该插入在right下一个，所以返回时+1
        //  return  right + 1   --没毛病-.-
        //3.目标值在数组所有元素之后的情况 [left, right]， return right + 1
        int length = nums.length;
        int left  =0;
        int right = length -1;
        while (left<=right){
            int middle  = (right+left)/2;
            if(target<nums[middle]) {
                right =middle-1;//在左区间[left,middle-1]  ,左闭右闭
            }else if(target>nums[middle]) {
                left =middle+1;//在左区间[middle+1,right]  ,左闭右闭
            }else return middle;
        }
        return  right+1;
    }
    //二分法第二种写法：代码中定义 target 是在一个在左闭右闭的区间里，**也就是[left, right)（这个很重要）**
    //如果说定义 target 是在一个在左闭右开的区间里，也就是[left, right) 。
    //不变量是:[left, right)的区间，在循环中坚持target 在 [left, right)区间的事实不变。
    public int searchInsert2_2(int[] nums, int target) {
        int length = nums.length;
        int left  =0;
        int right = length;
        while (left<right){//满足target 在 [left, right)区间 while (left<right) 就不能加==
            //当目标值插入数组中的位置 [left, right)时，
            //最后一次【比较后】必定  left = right = middle,跳出循环,return right
            int middle  = (right+left)>>1;
            if(target<nums[middle]) {
                right =middle;//在左区间[left,middle-1)  ,左闭右闭
            }else if(target>nums[middle]) {
                left =middle+1;//在左区间[middle+1,right)  ,左闭右闭
            }else return middle;
        }
        return  right;
    }

}
